#include <vector>
#include <stack>
using namespace std;
class Solution {
public:
    int largestRectangleArea(vector<int> &height) {
        int ans=0;
        stack<pair<int, int> > s;
        s.push(make_pair(0,-1));
        height.push_back(0);
        for (int i=0;i<height.size();i++) {
            int position=i;
            while (!s.empty() && s.top().first>=height[i]) {
                position=s.top().second;
                if (ans<(i-s.top().second)*s.top().first) ans=(i-s.top().second)*s.top().first;
                s.pop();
            }
            s.push(make_pair(height[i], position));
        }
        return ans;
    }
};
